import collections
import copy


class Solution:
    def append_one_to_sta(self, sta_list, one_group):
        if one_group[0] != '':
            one_group[1] = 1 if one_group[1] == '' else int(one_group[1])
            sta_list.append(copy.deepcopy(one_group))
        one_group = ['', '']
        return one_group

    def get_sub_formula(self, sta_list):
        sub_list = []
        sta_list.pop(-1)
        while sta_list[-1] != '(':
            sub_list.insert(0, sta_list[-1])
            sta_list.pop(-1)
        sta_list.pop(-1)
        return sub_list

    def process_sub_formula(self, sub_formula, cnt):
        cnt = 1 if cnt == '' else int(cnt)
        for e in sub_formula:
            e[1] *= cnt
        return sub_formula

    def fininal_process(self, sta_list):
        sta_list.sort()
        counter = collections.Counter()
        for e in sta_list:
            counter[e[0]] += e[1]
        ret = ''
        for e in counter:
            ret += e
            if counter[e] > 1:
                ret += str(counter[e])
        return ret

    # 输入的字符串先找出括号及跟着的数字部分
    # 利用子函数将括号展开，确保输入的只有一个配对括号
    # 最后一层括号去掉后，按顺序排序
    def countOfAtoms(self, formula: str) -> str:
        sta_list = []
        one_element_cnt = ['', '']
        idx = 0
        while idx < len(formula):
            c = formula[idx]
            if c == '(':
                one_element_cnt = self.append_one_to_sta(sta_list, one_element_cnt)
                sta_list.append(c)
            elif c.isupper():
                one_element_cnt = self.append_one_to_sta(sta_list, one_element_cnt)
                one_element_cnt[0] = c
            elif c.islower():
                one_element_cnt[0] += c
            elif c.isnumeric():
                one_element_cnt[1] += c
            elif c == ')':
                one_element_cnt = self.append_one_to_sta(sta_list, one_element_cnt)
                sta_list.append(c)
                idx += 1
                sub_cnt = ''
                while idx < len(formula) and formula[idx].isnumeric():
                    sub_cnt += formula[idx]
                    idx += 1
                sub = self.process_sub_formula(self.get_sub_formula(sta_list), sub_cnt)
                sta_list.extend(sub)
                continue
            idx += 1
        self.append_one_to_sta(sta_list, one_element_cnt)
        return self.fininal_process(sta_list)


formula = "K4(ON(SO3)2)2"
formula = 'Mg(OH)2'
formula = "Be32"
formula = "(H)"
test = Solution()
print(test.countOfAtoms(formula))
